import java.util.Arrays;

public class TriangleNumber {

    public static void main(String[] args) {
        int[] nums = {1,1,3,4};
        System.out.println(new TriangleNumber().triangleNumber(nums));
    }

    public int triangleNumber1(int[] nums) {
        int n = nums.length;
        if (n < 3) return 0;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                int l = j;
                int r = n - 1;
                int max = nums[i] + nums[j];
                while (l < r) {
                    int mid = (l + r) / 2 + 1;
                    if (nums[mid] >= max) {
                        r = mid - 1;
                    } else l = mid;
                }
                ans += l - j;
            }
        }
        return ans;
    }

    public int triangleNumber(int[] nums) {
        int n = nums.length;
        if (n < 3) return 0;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = n - 1; i >= 2; --i) {
            int l = 0;
            int r = i - 1;
            while (l < r) {
                if (nums[l] + nums[r] > nums[i]) {
                    ans += r - l;
                    --r;
                } else ++l;
            }
        }
        return ans;
    }
}
